Slashdot stories can be listened to in audio form via an RSS feed, as read by our own robotic overlord.

 



Forgot your password?
typodupeerror
Math Privacy Encryption

Improperly Anonymized Logs Reveal Details of NYC Cab Trips 192

Posted by Unknown Lamer
from the check-your-proof dept.
mpicpp (3454017) writes with news that a dump of fare logs from NYC cabs resulted in trip details being leaked thanks to using an MD5 hash on input data with a very small key space and regular format. From the article: City officials released the data in response to a public records request and specifically obscured the drivers' hack license numbers and medallion numbers. ... Presumably, officials used the hashes to preserve the privacy of individual drivers since the records provide a detailed view of their locations and work performance over an extended period of time.

It turns out there's a significant flaw in the approach. Because both the medallion and hack numbers are structured in predictable patterns, it was trivial to run all possible iterations through the same MD5 algorithm and then compare the output to the data contained in the 20GB file. Software developer Vijay Pandurangan did just that, and in less than two hours he had completely de-anonymized all 173 million entries.
This discussion has been archived. No new comments can be posted.

Improperly Anonymized Logs Reveal Details of NYC Cab Trips

Comments Filter:
  • "Oops"

    -New York

      • Cue the DMCA. (Score:2, Insightful)

        by Anonymous Coward

        In other news, the credentials for their plug-n-play coffee machine are 'admin' 'admin', and their gym locker combo is 1234. Someone made a half-assed attempt to obfuscate some data that nobody cares about (unless your husband's a cheating cabbie, I guess) and someone cracked it. News?

  • by FlyHelicopters (1540845) on Monday June 23, 2014 @07:05PM (#47301949)

    Too many governments and corporations continue to fail to understand that it requires having experts who actually know what they are doing be in charge of data security.

    This doesn't mean you contract it out to the lowest bidder or hire the cheapest CS degree you can find.

    It means you hire knowledge and experience, you hire expert skills, and those cost money.

    • Re: (Score:3, Insightful)

      In this case, it sounds like whoever got handed the job just couldn't, didn't care to, or was overruled about, thinking like an attacker.

      There are probably subtler methods of de-anonymizing the data that would require nontrivial skill to think of and counter; but it's a bit surprising to see somebody who knows enough about manipulating data to pull 20GB of records and hash a single field in each one without hurting himself or munging the result; but doesn't think "Medallion numbers are written on cabs. S
      • Adding a salt is a trivial way of fixing this.

        • Adding a salt is a trivial way of fixing this.

          No it aint.

        • by m.dillon (147925)

          Except you can decode the salt trivially if you took a cab ride that happens to be in the data set and you recorded the license and medallion number. At which point the salt is useless.

          -Matt

          • It does make your table 'o handy precomputed hashes unhelpful; but on such a computationally trivial keyspace that barely matters.

            I wonder if the choice of hashing, rather than substituting a UUID, was based on not thinking through the weakness of a hash under the circumstances, or based on the extra difficulty of making sure that the same UUID is substituted for the same hack and medallion number in all instances? It's not a whole lot of additional difficulty; but the tipping point has to live somewhere
            • What part of the story used ANY precomputed rainbow tables? None.

              salt + "1234", if you know the "1234" then its a tiny brute force to get the salt.

        • by msauve (701917)
          Using a one time pad is even easier.
          • For taxi cabs?

            • by msauve (701917) on Monday June 23, 2014 @09:28PM (#47302889)
              Sure. I'm assuming there's a requirement to have a unique transformation of medallion numbers (otherwise, you wouldn't have to include even a hashed version)...

              Instead of applying some hash to the medallion number, just do something like:
              Change all appearances of the first number in the list to "1". Change all appearances of the next unique medallion number in the list to "2." Etc.

              The result is in essence a OTP. Unless records of the process are kept, it's irreversible (lacking external info, such as medallion number x picked up a fare at location y at time z and correlated info is in the info provided)..
              • Re: (Score:2, Insightful)

                I'm appalled that your post has been modded "informative." Please do us all a favor and abstain from any future posts on cryptography. Instead, I recommend you spend your time with resources like Applied Cryptography [schneier.com]. Seriously, please put down the shovel, and if you're doing anything involving crypto for a living, please do the world a favor and resign today.

                • Anonymising the data just requires replacing each key with something unrecognisable. The GP's suggestion passes the smell test, though I would suggest randomising the list instead of assigning id values sequentially.
                • by N1AK (864906)
                  It is informative. Unless you knew that a particular record in the dataset was for a specific medallion/plate combo then what he's suggesting is sufficient to obscure the driver. If you did know that then you couldn't obfuscate the data without making it impossible to tell which records relate to the same (known) vehicle. If you're happy to do that then you could just not include any reference to either medallion or plates in any format in the data.

                  I'm not remotely surprised that someone on the internet
                  • by msauve (701917)
                    philip.paradis is simply being a assholish troll.

                    The original medallion and license(?) numbers need to be transformed into unique but consistent identifiers in the output, so one can still follow an individual cab/driver, but not be able to identify them in the real world.

                    Assuming the dataset is ordered in some way (such as by date and time, which seems logical), even changing each cab/driver number to a unique, truly random number wouldn't be any more secure than the sequential assignment I gave as an ex
                    • You're still completely wrong. I'm willing to spend my own money to ship you hardcopy references that will help you better yourself, in the hope that you will stop dispensing the sort of horrid advice you're continuing to regurgitate here. Why aren't you willing to take me up on this offer? Are you unable to provide a shipping address of any sort?

                    • by msauve (701917)
                      Repeating an incorrect statement doesn't make it correct. You're really not very good at trolling, or much of anything it seems.
                    • Why won't you accept a shipment of formal reference materials?

                • by ultranova (717540)

                  I'm appalled that your post has been modded "informative."

                  I'm appalled that yours has been modded "Insightful" despite having no content beyond a verbose "you suck".

                  • You must have missed the motherfucking literary reference I linked. Read the fucking book (and hopefully a few more), you fucking retard.

                    • by ultranova (717540)

                      You must have missed the motherfucking literary reference I linked. Read the fucking book (and hopefully a few more), you fucking retard.

                      The book you linked to is about cryptography, not incest pornography as you seem to be implying. Neither of these seems relevant to anonymising - as opposed to encrypting - records.

                      Good luck with treating your Tourette's, BTW. Or hangover. Whichever is relevant here.

                    • Are you confirming shipment of the book (along with a couple of other volumes) to Delft University of Technology [slashdot.org] in your care? I found it odd that even an undergraduate at such an institution would not already have access to such material, but perhaps all university copies are already on loan to other students. As an aside, you appear to be lacking the capacity to distinguish emphasis borne of extreme frustration from certain pathological afflictions. You should work on that.

                    • By the way, thanks for the added laughs per your attempt to reframe this discussion as "anonymising" versus "encrypting." You'd get a few charity points for sophomoric debate tactics if the subject matter were a bit less serious in nature, but that particular bit of commentary is indeed nothing more than a juvenile attempt at diverting attention from the matters at hand. Try again.

                  • Look, seriously, provide an address and I'll ship you a fucking copy of the book. Your choice.

                    • Thank you. I'll dispatch the shipment in a few hours in the care of "ultranova", provided I get a response back under that user account indicating confirmation of the destination address. I'll provide a post tracking reference here once the shipment is confirmed to be in transit.

        • This is correct. MD5(salt + data). Salt is same for EVERY MD5 operation. Create the file and then delete the salt, done. This is called keying.

      • by AmiMoJo (196126) *

        It was probably just overconfidence. Someone googled the solution, thought it didn't look hard, and told their boss they could take care of it and save $$$ in the process.

    • by Opportunist (166417) on Monday June 23, 2014 @08:33PM (#47302541)

      You can contract it out to the lowest bidder without a problem. There only have to be 2 clauses in the contract:

      1) You have a GOOD ITSEC company audit the shit out of it before it goes live.
      2) If the audit reveals that the company taking the contract don't know jack about security, THEY will pay for the audit and THEY will improve the software until they think it's finally good enough.

      1 and 2 are repeated until 1 turns out good.

      I worked for a very long time in government. And I learned one thing: You are not supposed to know shit. You are supposed to buy knowledge.

      • by chriscappuccio (80696) on Monday June 23, 2014 @10:44PM (#47303249) Homepage

        Sorry but unless you define "GOOD ITSEC company audit the shit out of it" in tangible terms that can actually hold someone liable for failure in a real way, this is just baloney. And if you define it with teeth, the price will increase. Basically, to define it properly, you'd be able to do it yourself. Oops.

      • by SeaFox (739806)

        I worked for a very long time in government. And I learned one thing: You are not supposed to know shit. You are supposed to buy knowledge.

        Isn't that how the entire job market works? That's why we have the education loan bubble we have -- employers don't believe you know anything without a piece of paper showing you spent thousands of dollars to learn it.

    • by gweihir (88907)

      It is not a surprise when you consider where else they mess up spectacularly. It is like there is no active intelligence to be had in these organizations.

    • by penix1 (722987) on Monday June 23, 2014 @09:21PM (#47302855) Homepage

      From TFS...

      City officials released the data in response to a public records request and specifically obscured the drivers' hack license numbers and medallion numbers...

      How many of you here have had to deal with a Freedom Of Information Act (FOIA) request which is what a "public records request" is? I have had the pleasure over a dozen times. You have 10 days to respond to that request in my state. Some states it is even less. Failure to do so can result in stiff penalties. 10 days is hardly enough time to contract out to someone and have the job "done right".

      It means you hire knowledge and experience, you hire expert skills, and those cost money.

      And you are happy to have your taxes raised to pay those fees? Riiiight!

      • Small problem.
        Taxi Hack numbers are available in a publicly accessible data base.
        A determined individual probably could find license numbers, they may be publicly accessible.
        Failure to understand the vulnerability is the design failure.
        A simple solution would have been to order the hashes numerically and re-number them cardinally. ie. 1,2,3 ...
        Would take less than a minute, for someone than knew how.
        Perhaps a few hours if the right person had to be tracked down.
        Never release source data.
      • by sexybomber (740588) <<moc.liamg> <ta> <oniliccob>> on Monday June 23, 2014 @10:34PM (#47303197)

        Your State may be different, but New York's Freedom of Information Law (or FOIL, we like to be different) works like this:

        The agency has to respond within five business days, but that response can read something like:

        Dear Sexybomber:

        We have received your request for public records pursuant to FOIL. Due to the complexity of the records you have requested, it may not be possible to produce them within the standard 20-day statutory period. We anticipate that we will be able to produce the records you have requested within 40 days. If you have questions or concerns, please direct them in writing to the address above.

        If they run into a snag, they have to inform you of this and produce the records within a "reasonable period".

        So it's not like NYC was under a five-day time crunch here. They could easily have responded and said it would take 40 or 60 days, being as there were several million records requested. That's definitely long enough to bring in a consultant (or even one of the more technically-literate staff members) to properly secure the data.

      • Hint: 30 seconds of my time leads me to believe this applies to you: Pennsylvania’s New Right to Know Law [state.pa.us]. If I'm in error on the state in question, please let me know, and I'll be more than glad to guide you to the appropriate legislation for your jurisdiction.

  • Cue a CFAA trial and a long stay in a cozy federal PMITA penitentiary.
  • by rsborg (111459) on Monday June 23, 2014 @07:12PM (#47301983) Homepage

    Large organizations will consistently fail to hire/staff competent people for data security related issues, and will push back on fines or punitive findings by criminalizing publicizing their incompetence.

    Thus sending all such talent straight to criminals who'll be happy to reward them with hard cash.

    It's like these guys _want_ a dystopian future.

  • by Krishnoid (984597) on Monday June 23, 2014 @07:21PM (#47302041) Journal

    Software developer Vijay Pandurangan did just that, and in less than two hours he had completely de-anonymized all 173 million entries.

    Having thereby run afoul of the circumvention of copyright protection mechanisms clause of the Digital Millenium Copyright Act, he was then subjected to the NYPD's controversial new program [theonion.com], and subsequently incarcerated.

  • by WaffleMonster (969671) on Monday June 23, 2014 @07:54PM (#47302281)

    Always assumed anywhere term "anonymized data" is used it is more likely than not to be companies and governments paying lip service to its customers... where data could easily be reversed into an identifiable way by either taking advantage of insufficient entropy or cross referencing datasets.

    There is after all no cost for violating privacy or unnecessary risk exposure associated with disclosure.

    One of my favorite examples of dangers of insufficient entropy stem from a PCI DSS requirement written by "experts" who should know better.

    3.4 Render PAN unreadable anywhere it is stored (including on portable digital media, backup media, and in logs) by using any of the following approaches:

    One-way hashes based on strong cryptography, (hash must be of the entire PAN) ...

    Search space of typical 16-digit card numbers is no match for a modern CPU once you have taken check digit, card type, issuer and issuer specific numbering into account... "strong cryptography" can't fix stupid.

    • by gweihir (88907)

      Indeed. Any reversible transformation for a small-entropy source set is insecure. Anybody that actually understands crypto knows that. Seems this mess is just one more indicator that some people hire far too cheap when it gets to IT.

    • by swillden (191260)

      Always assumed anywhere term "anonymized data" is used it is more likely than not to be companies and governments paying lip service to its customers... where data could easily be reversed into an identifiable way by either taking advantage of insufficient entropy or cross referencing datasets.

      It's worth mentioning that one possible solution in this sort of situation is to use a keyed hash. Assuming a good base hash (which MD5 really isn't, any more, but HMAC MD5 would likely have been fine) and a well-secured key with sufficient entropy, it is infeasible to reverse the hash. Cross-referencing may still be an issue, though straight brute force reversing of the hashing isn't. To eliminate the possibility of cross-referencing it's necessary to use a different hash key for each database.

      Of course,

    • Um, the standard is fine. The phrase "One-way hashes based on strong cryptography" means (to any professional in the business) that one must salt [wikipedia.org] the hash with sufficient entropy to make brute-forcing the input space impossible. So 16 digit CC has little entry, but add a 16-byte hash and you've somewhere.

      So yeah, "strong cryptography" can't fix stupid, but those that know how to use it are plenty fine.

      • Um, the standard is fine. The phrase "One-way hashes based on strong cryptography" means (to any professional in the business) that one must salt the hash with sufficient entropy to make brute-forcing the input space impossible. So 16 digit CC has little entry, but add a 16-byte hash and you've somewhere.

        This is the second time 'use salts' has been mentioned. Salts are not secret keys and only provide protection against creation of lookup tables to accelerate brute force of multiple items... they in no way address the underlying problem of insufficient entropy.

        I don't know the exact figure last I looked into this space of every possible credit card that can be issued across all currently known issuers is well less than a trillion most likely in tens to hundreds of billions range... practically free by tod

        • Re: (Score:3, Interesting)

          by Buzer (809214)

          Salts do provide protection against that. Salts are secret if you want them to be (you can protect the plain text salt same way as you do protect your plain text keys for encryption), you only need to share them when other party has to be able to hash their original data.

          Here are some sha1 hashes:

          • 4c2199828f355281e0f6eccb76d9df609f99ed0e salt+"123"
          • 458183225b77f6baff7c4c439b0ed3a5e7278e8a salt+"456"
          • ed974fc96c530639cccc9b18315396789d93a697 salt+"789"
          • f87a2fa039a20d01032f19b5852868343f3d06b9 salt+"???"

          So, how a

          • by swillden (191260)

            Salts are secret if you want them to be

            If you keep them secret then they're not salts, they're keys. The definition of "salt" in the cryptographic world includes the notion that it need not be kept secret, just as "IV" is a value which need not be secret but must not be predictable, and "nonce" is a value which need not be secret or predictable (indeed a salt is technically a form of or application of a nonce).

            Another characteristic of salts is that you use a different salt for each entry. That's counterproductive in the case being discussed,

  • For this application, MD5 did not make a difference. SHA512 would have been just as insecure. For some applications, MD5 is perfectly secure if used competently. This example is one and the original story doe snot claim any culpability on the part of MD5. As always, there is no substitute for knowing what you are doing.

  • I de-anonymized this comment by signing in.

  • Using any public hash exposes you to dictionary attacks. Especially when you publish which one you've used.
    The quality of the encryption is irrelevant.
    Security through obscurity, using a custom algorithm, is the only way.
    Taking MD5, it's published, and tweaking a few points (though who ever did this needs to be very competent) would have been sufficient.

    Some manager probably said any work for addition security wasn't worth the cost. Ooops!
    • by PPH (736903)

      Security through obscurity, using a custom algorithm, is the only way.

      Not necessarily. I imagine the reason the hashed field was included in the published logs was to provide a key to group results by driver. Even if that driver was to remain anonymous. So all the city would have had to do is issue a system generated UID for each medallion/license number combination and populate the published data with that.

      Nobody knows who driver 1, 2, 3, .., 736903, ... etc. are. But one can still analyze per-driver data.

      • nope, it has to do with the key. given a tag # and license # you can dictionary attack the hash. especially since the the source data is known, easy to break.

        they didn't pre-anonamize the keys
        • by swillden (191260)

          nope, it has to do with the key. given a tag # and license # you can dictionary attack the hash. especially since the the source data is known, easy to break.

          If they'd used a keyed hash of tag # and license #, it wouldn't have been breakable. Even HMAC-MD5 would have been fine, given sufficient entropy in the key, though I'd have used HMAC-SHA256 just as a matter of good crypto hygiene.

          And a custom algorithm is wrong, wrong, wrong. That's just begging for weakness in the solution. Use the proper standard algorithm for the job.

    • by Vellmont (569020) on Monday June 23, 2014 @10:16PM (#47303101) Homepage

      Taking MD5, it's published, and tweaking a few points (though who ever did this needs to be very competent) would have been sufficient.

      No, that would have been stupid. It's unlikely someone would have reverse engineered your hacked md5 algorithm, but it's also possible you could screw it up.

      The solution is VERY simple. Generate a random 256 bit string. Hash random-string+data, and use the output as the identifier. Throw away the random 256 bit string.


      Some manager probably said any work for addition security wasn't worth the cost. Ooops!

      No, some developer didn't know what the hell they were doing. You'd be surprised (but shouldn't be) how little most developers know about security, especially encryption.

      • well, you just described a way to tweak an algorithm.
        wouldn't even have to go to a 256 bit key. Doing that into MD5 would probably foil anything less than a concerted financial attack.
        No media outlet could afford the computing power to attack that.
        I used the same approach, with some further tweaks to secure financial communications a decade ago.

        Lack of understanding security doesn't surprise me. I'm an engineer who does. I designed and wrote a suite that passed a 3d party, hostile, security audit.
        • by Vellmont (569020)

          No, that's not a tweak to an algorithm, it's a random input to an algorithm. The algorithm is the same, the input is different.

        • by swillden (191260)

          I designed and wrote a suite that passed a 3d party, hostile, security audit.

          I don't normally play the credential game, but if that's what you want to do...

          Me too. Many times. Including once an audit by the NSA (back when they actually tried to strengthen security). I've also been a security consultant for dozens of fortune 500 companies, and similarly-sized international corporations around the world. I've consulted for the US and Israeli militaries. I'm currently a crypto security engineer at Google, and the lead maintainer of a popular open source crypto library. I'm not a real

      • by swillden (191260)

        The solution is VERY simple. Generate a random 256 bit string. Hash random-string+data, and use the output as the identifier.

        This. Except rather than hashing the key with the data, use a proper keyed hash construction. HMAC is a good choice.

      • by nabsltd (1313397)

        The solution is VERY simple. Generate a random 256 bit string. Hash random-string+data, and use the output as the identifier. Throw away the random 256 bit string.

        How is this any more secure than assigning a the random 256 bit string as the identifier (with collision prevention, of course)?

        Next, how would a random sort of the original keys (SELECT DISTINCT medallion_number FROM the_table ORDER BY RANDOM) followed by assigning 1..number_of_medallions to use as the identifier be less secure?

        As others have stated, you could even just assign the new identifier sequentially if the source table isn't sorted by the key you are trying to obscure.

Our business is run on trust. We trust you will pay in advance.

Working...