Martinovic et al. proposed a Brain-Computer-Interface (BCI) -based attack in which an adversary is able to infer private information about a user, such as their bank or area-of-living, by analyzing the user's brain activities. However, a key limitation of the above attack is that it is intrusive, requiring user cooperation, and is thus easily detectable and can be reported to other users. In this paper, we identify and analyze a more serious threat for users of BCI devices. We propose a it subliminal attack in which the victim is attacked at the levels below his cognitive perception. Our attack involves exposing the victim to visual stimuli for a duration of 13.3 milliseconds -- a duration usually not sufficient for conscious perception. The attacker analyzes subliminal brain activity in response to these short visual stimuli to infer private information about the user. If carried out carefully, for example by hiding the visual stimuli within screen content that the user expects to see, the attack may remain undetected. As a consequence, the attacker can scale it to many victims and expose them to the attack for a long time. We experimentally demonstrate the feasibility of our subliminal attack via a proof-of-concept study carried out with 27 subjects. We conducted experiments on users wearing Electroencephalography-based BCI devices, and used portrait pictures of people as visual stimuli which were embedded within the background of an innocuous video for a time duration not exceeding 13.3 milliseconds. Our experimental results show that it is feasible for an attacker to learn relevant private information about the user, such as whether the user knows the identity of the person for which the attacker is probing.