wu :: forums
« wu :: forums - Security by obscurity in 100 bits »

Welcome, Guest. Please Login or Register.
Dec 10th, 2024, 12:02pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, SMQ, towr, Grimbal, william wu, ThudnBlunder, Icarus)
   Security by obscurity in 100 bits
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Security by obscurity in 100 bits  (Read 991 times)
ephyzy
Newbie
*





   


Gender: male
Posts: 27
Security by obscurity in 100 bits  
« on: Jun 13th, 2016, 4:31am »
Quote Quote Modify 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 13th, 2016, 5:40am by ephyzy » IP Logged
ephyzy
Newbie
*





   


Gender: male
Posts: 27
Re: Security by obscurity in 100 bits  
« Reply #1 on: Jun 14th, 2016, 4:01am »
Quote Quote Modify 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 14th, 2016, 4:02am by ephyzy » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Security by obscurity in 100 bits  
« Reply #2 on: Jun 18th, 2016, 1:14pm »
Quote Quote Modify 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: male
Posts: 27
Re: Security by obscurity in 100 bits  
« Reply #3 on: Jun 18th, 2016, 2:06pm »
Quote Quote Modify 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
ephyzy
Newbie
*





   


Gender: male
Posts: 27
Re: Security by obscurity in 100 bits  
« Reply #4 on: Nov 19th, 2024, 2:47am »
Quote Quote Modify Modify

Any ideas or takers for the alternative problem statement? My Python code in 2016 was actually wrong, as I found out about a month later. Seeking a non-brute force method if possible. The upper limit of N is 10^9.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board