I'm stealing Viorel's demo, to show a simplification:
declare @table table ( [Certificate] varbinary(max) )
insert @table values
( 0x112233AABBCC778899 ),
( 0x1122330ABBCC778899 ),
( 0x112233445566778899 )
SELECT * FROM @table WHERE charindex(0x33AABB, Certificate) > 0
That is, no need to cast to varchar(MAX). Charindex can operate on vbarbinary. And that will be quite a bit faster, since it will be a binary comparison.