4 ms·
Determine the resistance of hashed InChI keys to brute-force attacks. The IUPAC InChI keys are a nomenclature to turn chemical structures, like morphine, into
by dalke 14y ago
Determine the resistance of hashed InChI keys to brute-force attacks.
The IUPAC InChI keys are a nomenclature to turn chemical structures, like morphine, into a unique linear representation, like InChI=1S/C17H19NO3/c1-18-7-6-17-10-3-5-13(20)16(17)21-15-12(19)4-2-9(14(15)17)8-11(10)18/h2-5,10-11,13,16,19-20H,6-8H2,1H3/t10-,11+,13-,16-,17-/m0/s1 .
This string is too long, so there is a way to use SHA-256 to convert the above into a hashed string BQJCRHHNABKAKU-KBQPJGBKSA-N, where the first 14 characters are the basic topology, and the successive 9 characters contain the other information.
Some people believe that this can be used to query the web for "secret" information. That is, you work at a pharma and want to know if others know about compound X. If they don't know about X then you don't want to tell the about it. Otherwise it reveals information about new compounds that you are working on.
You instead search for hash(X). If others have hash(X) then you're revealing less information, since this is likely a publicly known structure. If others don't have hash(X) than you might conclude that you have a proprietary structure and haven't revealed enough information for others to know what you are working on.
I don't believe that the hash key is appropriate for this. I think it is open to a brute force attack.
While 26 * * 14 is very large, most people work inside "chemical space" of reasonable drug-like compounds. The Reymond group has enumerated, in GDB-13, all drug-like containing up to 13 atoms of C, N, O, S, and Cl, which is 977 million compounds. If you convert these to InChI hashes, then you might be able to guess the core scaffold given an unknown InChI hash.
Once you have the core structure, you might then be able to brute force the bond and hydrogen assignment.
This can be tested by taking GDB-13 and finding the InChI hashes. You may need to enumerate over a range of hydrogens for each one, giving some several billion keys. Then take, say, the ChEMBL data set (for N<=13 heavy atoms) as the source for the "secret" keys, and generate their hashes. Are there matches? What percentage of topologies can be found this way?
If you can find the topologies, can you then as phase 2 deduce the overall structure, and if so, what percentage?
As a quick estimate, phase one (enumerating GDB-13 InChI keys) would take over 10 years on my desktop, and 5 TB of disk. That's about perfect for a supercomputer job, and you can select subsets as a appropriate based on the available time. (Eg, pick only the C, N, O, S subset of GDB-13 and ChEMBL and you've reduced your space by a lot.)
I don't know what's needed for phase 2 and can provide no estimate.
- dekhn 14y agoAndrew, this is an embarassingly parallel problem. The supercomputer hardware (interconnect) would be simply wasted. If you provide C++ source code that can be compiled with Native Client, and a list of tasks to run (binary command lines), Exacycle (http://googleresearch.blogspot.com/2012/12/millions-of-core-hours-awarded-to.html http://googleresearch.blogspot.com/2012/12/millions-of-core-...) is more appropriate. Based on our publicized results this wouldn't take very long (10 years on a desktop = less than an hour on Exacycle; you'd spend more time writing the program and the data analysis than the actual runtime). however, I don't really see this problem as a high priority. pharma has bigger problems than to probe remote websites to find out what their competitors might be interested in.
- 0x0 14y agoWhy is Google insisting on the use of NativeClient? Not insinuating anything, but a NaCl-compiled distributed task would be an excellent fit for farming out to unsuspecting browser clients. (Reminds me about that sneaky javascript-based bitcoin miner that was injected on a few web sites some time ago)
- jey 14y agoBecause NaCl is a fully sandboxed way to run full-performance native code.
- dekhn 14y agoWe looked at several security and sandbox technologies, and NaCl was closest to our requirements: near-native performance, easy access to the NaCl software development team and supported C and C++. Strictly speaking, we use it as a "Native Server", rather than a "Native Client" (it runs on server-class machines, not desktop browsers). We've talked with Vijay Pande (of Folding@Home fame) about making "Folding@Chrome", but that would be opt-in (IE, you'd install a Chrome App). If you have an alternative sandbox and security framework, I'd be happy to hear about it.
- 0x0 14y ago