Author 
Topic: Security by obscurity in 100 bits (Read 351 times) 

ephyzy
Newbie
Gender:
Posts: 26


Security by obscurity in 100 bits
« on: Jun 13^{th}, 2016, 4:31am » 
Quote Modify

A "security by obscurity" system uses a 100 bits access code, with only 12 bits set. On the first day, it had a random access code of 100 bits. Then at the end of the day, it collects all the N intrusion attempts for the day (each one is 100 bits, with only 6 set bits) and updates its access code for the next day. This update is done in such a way that:  a% is correct on any 6 set bits,  b% is correct on any 5 set bits,  c% is correct on any 4 set bits,  d% is correct on any 3 set bits,  e% is correct on any 2 set bits  f% is correct on any 1 set bit  g% is correct on no set bits  If all the bits set by the above 7 rules are less than 12, the system sets some random bits to make up the 12. Q1: How must the new access code be generated at the end of the day, in terms of N intrusion attempts and the positive real numbers a, b, c, d, e, f, g (generated by the system such that the sum of these 7 is exactly 100)? Q2: Question 1, but for fixed values of a,b,c,d,e,f and g on every day. P.S. The system only provides direct access to set 6 bits. An intruder does not know that it is 12 bits that will need to be set, as the other 6 bits are hidden.

« Last Edit: Jun 13^{th}, 2016, 5:40am by ephyzy » 
IP Logged 



ephyzy
Newbie
Gender:
Posts: 26


Re: Security by obscurity in 100 bits
« Reply #1 on: Jun 14^{th}, 2016, 4:01am » 
Quote Modify

Alternative problem statement: Each of matrices P, Q, R is a column matrix with 100 bit binary numbers. Given a matrix P, where each entry has exactly 6 set bits but the rows are not necessarily identical. What strategies / procedures can be used to generate a matrix Q with identical rows (some binary number with any 12 bits set) such that upon taking a bitwise AND of P and Q (i.e. P & Q) we may obtain any matrix R whose entries have set bits that have a known statistical distribution between 0 and 6?

« Last Edit: Jun 14^{th}, 2016, 4:02am by ephyzy » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13596


Re: Security by obscurity in 100 bits
« Reply #2 on: Jun 18^{th}, 2016, 1:14pm » 
Quote Modify

I don't really fancy my chances that it's even possible to get close to a given statistical distribution. If it is, brute force seems almost doable, 100!/(88! * 12!) is only in the order of 10^15. How large is N?


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



ephyzy
Newbie
Gender:
Posts: 26


Re: Security by obscurity in 100 bits
« Reply #3 on: Jun 18^{th}, 2016, 2:06pm » 
Quote Modify

@towr: Thanks! N can be as large as possible, and that's why I am wondering if there is a more efficient way to solve the problem that will scale well even for large N. I eventually solved this in a way that involves minimal randomization (successively choosing 2 or 3 random integers), and also involves some bitwise OR and AND operations, but I feel sure there is probably a better way to do it.


IP Logged 



