 |
|
|
|
|
|
 Title: |
US5442699:
Searching for patterns in encrypted data
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Arnold, William C.; Mahopac, NY
Chess, David M.; Mohegan Lake, NY
Kephart, Jeffrey O.; Yorktown Heights, NY
Sorkin, Gregory B.; New York, NY
White, Steve R.; New York, NY
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1995-08-15
/ 1994-11-21
|
| Application Number: |
US1994000342519
|
| IPC Code: |
Advanced:
G06F 1/00;
G06F 21/00;
G11B 23/28;
Core:
more...
IPC-7:
G11B 23/28;
|
| ECLA Code: |
G11B23/28B2; G06F21/00N3V4S;
|
| U.S. Class: |
Current:
713/188;
380/001;
726/024;
G9B/023.087;
Original:
380/004;
380/001;
380/025;
|
| Field of Search: |
380/001,4,25
|
| Priority Number: |
| 1994-11-21 |
US1994000342519 |
|
| Abstract: |
A searching method determines, given a specified encryption method (or set of encryption methods) and a specified pattern (or set of patterns), whether a given text contains an encryption, with any key, of anything fitting the pattern or patterns. The procedure detects and locates patterns that are present within data that has been encrypted, provided that the encryption method is one of a variety of simple methods that are often employed by computer programs such as computer viruses. The method includes: 1. applying an invariance transformation to the chosen pattern (or set of patterns) to be matched, to obtain a "reduced pattern"; 2. applying the same reduction to the encrypted data to obtain "reduced data"; 3. using standard string searching techniques to detect the existence of a match between the reduced pattern and the reduced data, thereby signalling the likely existence of the pattern in encrypted form within the encrypted data; 4. corroborating any such likely matches by using techniques specialized to the particular form of encryption; and 5. providing information about the match. Depending on the nature of the encryption method and the desired degree of certainty about the match, item 4 may not be necessary. In one embodiment, the patterns and an indication of the encryption method(s) for which they are appropriate are incorporated into the database of a computer virus searcher. The searcher applies each of several different invariant transformations to the searched data (one for each encryption method of interest), and uses search techniques, such as parallel search techniques currently employed by virus searchers, to detect any patterns that may be encrypted within the searched data.
|
| Attorney, Agent or Firm: |
Whitham, Curtis, Whitham & McGinn ;
Tassinari, Robert P. ;
|
| Primary / Asst. Examiners: |
Barron, Jr., Gilberto;
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 24 claims |
Having thus described our invention, what we claim as new and desire to secure by Letters Patent is as follows:
1. A method for determining whether a given text contains a given pattern, or any member of a class of possible encryptions of that pattern, or any member of a class of possible encryptions of patterns similar to the given pattern, the method comprising the steps of:
- (a) for each possible encryption of the given pattern,
- i. reducing the given pattern to a transformed pattern, the transformation having a property that it is invariant with respect to encryption of the given pattern with any allowable key,
- ii. reducing the given text to a transformed text, the transformation being the same as was applied to the given pattern,
- iii. searching for the presence of the transformed pattern, or a pattern similar to the transformed pattern, in the transformed text, and
- iv. identifying a match if the searching step detects the presence of the transformed pattern, or a pattern similar to the transformed pattern, in the transformed text.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 23 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G1995-292780
DERABS G1995-292780
|
| Other References: |
David Chess, "Virus Verification and Removal-Tools and Techniques", Virus Bulletin, dtd Nov. 1991, pp. 7-11.
Dan Greene, et al. "Multi-Index Hashing for Information Retrieval", dtd Jan. 4, 1994.
Sun Wu, et al. "Fast Text Searching with Errors", Department of Computer Science Bul, University of Arizona, dtd Jun. 1991.
|
|
 Nominate this for the Gallery...
|
|
